package com.lx.algorithm.unionFind;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * Description: 并查集
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-10-23 14:11:17
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-10-23     张李鑫                     1.0         1.0 Version
 */
public class unionFind<V> {
    //存储代表节点及代表节点的值
    private HashMap<V, Node> nodes;
    // 存储每个集合的大小
    private HashMap<Node, Integer> sizeMap;
    //存储每个节点的上一个节点
    private HashMap<Node, Node> parents;


    /**
     * <p>
     * 构造方法
     * 先创建三个hash表 然后把节点分别加到表里去
     * </p>
     *
     * @param list
     * @return
     * @Author zlx
     * @date 2021/10/23
     */
    public unionFind(List<V> list) {
        nodes = new HashMap<>();
        sizeMap = new HashMap<>();
        parents = new HashMap<>();

        for (V v : list) {
            Node node = new Node(v);
            nodes.put(v, node);
            sizeMap.put(node, 1);
            parents.put(node, node);
        }
    }

    public boolean isSameSet(V a, V b) {
        return findFather(nodes.get(a)) == findFather(nodes.get(b));
    }

    /**
     * <p>
     * 这里有一个优化.
     * 用栈优化
     * 创建一个栈 把沿途遍历到的节点都加入到栈里面去
     * 找到父亲节点
     * 在返回之前把加到栈里的节点全部都挂在父亲节点下面
     * </p>
     *
     * @param node
     * @return com.lx.algorithm.unionFind.Node
     * @Author zlx
     * @date 2021/10/23
     */
    private Node findFather(Node node) {
        Stack<Node> nodes = new Stack<>();
        while (parents.get(node) != node) {
            nodes.push(node);
            node = parents.get(node);
        }

        while (!nodes.isEmpty()) {
            Node pop = nodes.pop();
            parents.put(pop, node);
        }
        return node;
    }


    /**
     * <p>
     * 合并集合
     * </p>
     *
     * @param a
     * @param b
     * @return void
     * @Author zlx
     * @date 2021/10/23
     */
    public void union(V a, V b) {
        Node aFather = findFather(nodes.get(a));
        Node bFather = findFather(nodes.get(b));
        //如果相等说明他们已经属于一个集合了 所以不需要合并
        if (aFather != bFather) {
            Integer integer = sizeMap.get(aFather);
            Integer integer1 = sizeMap.get(bFather);
            Node max = integer > integer1 ? aFather : bFather;
            Node min = max == aFather ? bFather : aFather;
            parents.put(min, max);
            sizeMap.put(min, integer + integer1);
            sizeMap.remove(min);


        }
    }


}